package oj;

//平衡二叉树：给定一个二叉树，判断它是否是高度平衡的二叉树。本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
public class Solution_110 {
    public static int heightOf(TreeNode root){
        if(root == null){
            return 0;
        }
        int left = heightOf(root.left);
        int right = heightOf(root.right);
        return Integer.max(left,right) + 1;
    }
    public boolean isBalanced(TreeNode root) {
        if(root == null){
            return true;
        }
        if(!isBalanced(root.left)){
            return false;
        }
        if(!isBalanced(root.right)){
            return false;
        }
        //比较左右子树的高度差
        int left = heightOf(root.left);
        int right = heightOf(root.right);
        int diff = left - right;
        //高度差大于 1
        if(diff < -1 || diff > 1){
            return false;
        }
        return true;
    }
}
